package com.github.yangyishe.p200;

/**
 * 169. 多数元素
 * https://leetcode.cn/problems/majority-element/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [3,2,3]
 * 输出：3
 * 示例 2：
 *
 * 输入：nums = [2,2,1,1,1,2,2]
 * 输出：2
 *
 *
 * 提示：
 * n == nums.length
 * 1 <= n <= 5 * 104
 * -109 <= nums[i] <= 109
 *
 *
 * 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 *
 */
public class Problem169 {
    public static void main(String[] args) {
        int[] nums={3,2,3};

        Problem169 problem169 = new Problem169();
        int i = problem169.majorityElement(nums);
        System.out.println("beyond half size:"+i);
    }

    /**
     * 思路：
     * 使用B-M算法。
     * 其核心思路是：如果存在这样的核心元素，那么任意去除两个不同的元素，其余元素组成的核心元素，必定与原集合的多数元素相同。
     * 使用count对第一个出现的元素计数：如果后续遇到相同元素则COUNT+1，否则COUNT-1，以此表示去除两个不同元素的意思。
     * 如果该元素不是多数元素，则必定到集合中间的某个位置，就会提前遇到COUNT=0的情况。
     * 这时再找新的候选多数元素即可。
     * 真正的多数元素，最后的COUNT必定大于0。
     *
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        Integer cadidate=null;
        int count=0;

        for(int num:nums){
            if(count==0){
                cadidate=num;
            }
            count+=(cadidate==num)?1:-1;
        }

        return cadidate;
    }
}
